home *** CD-ROM | disk | FTP | other *** search
/ Language/OS - Multiplatform Resource Library / LANGUAGE OS.iso / cpp_libs / sos3-2.lha / src / agg / agg.sos < prev    next >
Text File  |  1991-10-24  |  20KB  |  523 lines
  1. /* --------------------------------------------------------------------------
  2.  * Copyright 1992 by Forschungszentrum Informatik (FZI)
  3.  *
  4.  * You can use and distribute this software under the terms of the licence
  5.  * you should have received along with this program.
  6.  * If not or if you want additional information, write to
  7.  * Forschungszentrum Informatik, "STONE", Haid-und-Neu-Strasse 10-14,
  8.  * D-7500 Karlsruhe 1, Germany.
  9.  * --------------------------------------------------------------------------
  10.  */
  11. /* ************************************************************************ */
  12. /*                            SOS aggregate classes                         */
  13. /* **************************** ************** **************************** */
  14.  
  15. with extern;
  16.  
  17. schema agg
  18. {
  19. typedef sos_Int Index;
  20.  
  21. // ******************************  Aggregate *******************************
  22.  
  23. class sos_Aggregate
  24. {
  25. public:
  26.    sos_Bool  is_empty ();        // TRUE iff card == 0
  27.    void      clear();                     // iterative application of remove_at
  28.                     // until the Aggregate is empty
  29.  
  30.    // ** Abstract operations **
  31.    // must be implemented by specific classes derived from sos_Aggregate
  32.  
  33.    abstract sos_Int       card ();    // return the cardinality
  34.  
  35.    // ** sos_Cursor operations (abstract) **
  36.  
  37.    abstract sos_Cursor    open_cursor (sos_Container = TEMP_CONTAINER);
  38.                     // create a new sos_Cursor for
  39.                     // this Aggregate.
  40.    abstract void          close_cursor (sos_Cursor);
  41.                     // remove the sos_Cursor
  42.    abstract sos_Cursor    duplicate (sos_Cursor);
  43.                     // create a new cursor on the same
  44.                     // entity
  45.    abstract sos_Bool      is_valid (sos_Cursor);
  46.                     // checks if the cursor is exceeded
  47.    abstract void          remove_at (sos_Cursor);
  48.                     // remove the 'current' entry from
  49.                     // the Aggregate and position the
  50.                     // cursor to the succeeding entry
  51.    abstract sos_Bool      to_first (sos_Cursor);
  52.                     // set the sos_Cursor to the first
  53.                     // entity
  54.    abstract sos_Bool      to_last (sos_Cursor);
  55.                     // set the sos_Cursor to the last entity
  56.    abstract sos_Bool      to_succ (sos_Cursor, sos_Int = 1);
  57.                     // position the cursor on the
  58.                     // succeeding entity; return TRUE
  59.                     // if such an entity exists
  60.    abstract sos_Bool      to_pred (sos_Cursor, sos_Int = 1);
  61.                     // position the cursor on the
  62.                     // preceding entity; return TRUE
  63.                     // iff such an entity exists
  64. }; // ** sos_Aggregate **
  65.  
  66.  
  67. class Collection<Entity> (sos_Bool based_on_equal = FALSE) : sos_Aggregate
  68.    // the create parameter determines whether the is_element()
  69.    // function is based on the 'equal' or the '==' function
  70. {
  71. public:
  72.    sos_Bool         is_element (Entity);  // check the membership of the Entity
  73.  
  74.    // ** Abstract operations **
  75.    // must be implemented by specific classes derived from Aggregate
  76.  
  77.    abstract Entity  get (sos_Cursor);     // return the 'current' Entity
  78.  
  79. protected:
  80.    sos_Bool         based_on_equal = based_on_equal;
  81.  
  82. }; // ** Collection<Entity> **
  83.  
  84.  
  85. // ****************************  Association *******************************
  86.  
  87. class Association<Role1, Role2> (sos_Bool role1_based_on_equal = FALSE,
  88.                  sos_Bool role2_based_on_equal = FALSE)
  89.    : sos_Aggregate
  90. {
  91. public:
  92.    sos_Bool        is_role1 (Role1);       // check the membership of the role1
  93.    sos_Bool        is_role2 (Role2);       // check the membership of the role2
  94.  
  95.    // ** Abstract operations **
  96.    // must be implemented by specific classes derived from Aggregate
  97.  
  98.    abstract Role1  get_role1 (sos_Cursor); // return the 'current' role1
  99.    abstract Role2  get_role2 (sos_Cursor); // return the 'current' role2
  100.  
  101. protected:
  102.    sos_Bool        role1_based_on_equal = role1_based_on_equal;
  103.    sos_Bool        role2_based_on_equal = role2_based_on_equal;
  104.  
  105. }; // ** Association<Role1, Role2> **
  106.  
  107.  
  108. // *******************************   sos_Cursor   **************************
  109.  
  110.  
  111. class sos_Cursor (sos_Aggregate domain)
  112. {
  113. public:
  114.    sos_Node   current;                    // the current node
  115.  
  116.    sos_Bool   defined_for (sos_Aggregate);// return TRUE iff the sos_Cursor has
  117.                       // been opened for sos_Aggregate
  118.  
  119. protected:
  120.    static void local_initialize (sos_Cursor);
  121.  
  122. private:
  123.    sos_Aggregate  domain = domain;        // aggregate the cursor is opened for
  124.  
  125. }; // ** sos_Cursor **
  126.  
  127.  
  128. // ******************************    List    *******************************
  129.  
  130. class List<Entity> (sos_Bool based_on_equal = FALSE)
  131.    : Collection<Entity> (based_on_equal)
  132. {
  133. public:
  134.    void          append (Entity);              // appends the element
  135.    void          insert (Index, Entity);       // insert the element before the
  136.                            // specified position
  137.                            // (i>l.card () | i==0) <=> l += e
  138.    void          remove (Index);               // remove the element at the
  139.                            // specified position
  140.    Entity        get_nth (Index);              // return the element
  141.                            // at the specified position
  142.    void          set_nth (Index, Entity);      // set the given element
  143.                            // at the specified  position
  144.  
  145.    // ** List operators **
  146.  
  147.    void         operator+= (List<Entity>);    // appends another list
  148.  
  149.    // ** sos_Cursor operations **
  150.  
  151.    Index        current_pos (sos_Cursor);         // returns current position
  152.    sos_Bool     move_cursor (sos_Cursor, Index);  // moves cursor to position
  153.    void         insert_before (sos_Cursor, Entity);
  154.    void         insert_after  (sos_Cursor, Entity);
  155.    void         set (sos_Cursor, Entity);      // replace the 'current' entity
  156.                           // by the given Entity
  157.  
  158.    // ** Redefinitions **
  159.  
  160.    Entity       get (sos_Cursor);        // redefined (-> Collection)
  161.  
  162.    void         remove_at (sos_Cursor);        // redefined (-> sos_Aggregate)
  163.    sos_Int      card ();            // redefined (-> sos_Aggregate)
  164.    sos_Cursor   open_cursor (sos_Container = TEMP_CONTAINER);
  165.                         // redefined (-> sos_Aggregate)
  166.    void         close_cursor (sos_Cursor);    // redefined (-> sos_Aggregate)
  167.    sos_Cursor   duplicate (sos_Cursor);        // redefined (-> sos_Aggregate)
  168.    sos_Bool     is_valid(sos_Cursor);        // redefined (-> sos_Aggregate)
  169.    sos_Bool     to_first(sos_Cursor);        // redefined (-> sos_Aggregate)
  170.    sos_Bool     to_last(sos_Cursor);        // redefined (-> sos_Aggregate)
  171.    sos_Bool     to_succ (sos_Cursor, sos_Int=1);// redefined (-> sos_Aggregate)
  172.    sos_Bool     to_pred (sos_Cursor, sos_Int=1);// redefined (-> sos_Aggregate)
  173.  
  174. protected:
  175.    static void     local_initialize (List<Entity>);
  176.    static void     local_finalize (List<Entity>);
  177.  
  178.    static void     local_assign (List<Entity>, sos_Object);
  179.    static sos_Bool local_equal (List<Entity>, sos_Object, sos_Eq_kind);
  180.    static sos_Int  local_hash_value (List<Entity>);
  181.  
  182. private:
  183.    local sos_List_node first, last;
  184.  
  185.    sos_Int       cardinality;
  186.  
  187. }; // ** List<Entity> **
  188.  
  189.  
  190. // ******************************   Array    *******************************
  191.  
  192. class Array<Entity> (Index bottom, Index top, sos_Bool based_on_equal = FALSE)
  193.    : Collection<Entity> (based_on_equal)
  194. {
  195. public:
  196.    Index        get_bottom ();
  197.    Index        get_top ();
  198.    Entity       get_nth (Index);    // returns the element at the
  199.                     // specified position
  200.    void         set_nth (Index, Entity);// replaces the element at the given
  201.                     // position by the given element
  202.    void         shift (Index start,    // shifts from given start index,
  203.                sos_Int number);    // the specif. number of elements
  204.                     // direction: + right / - left
  205.    void         rotate (sos_Int number);    // rotates number of positions
  206.  
  207.    // ** Array operators **
  208.  
  209.    Entity       operator[] (Index);
  210.  
  211.    // ** sos_Cursor operations **
  212.  
  213.    Index        current_pos (sos_Cursor);     // returns current position
  214.    sos_Bool     move_cursor (sos_Cursor, Index); // moves cursor to Index position
  215.    void         set (sos_Cursor, Entity);     // replace the 'current' entity
  216.                          // by the given Entity
  217.  
  218.    // ** Redefinitions **
  219.  
  220.    sos_Int          size();                // redefined (-> sos_Object)
  221.  
  222.    Entity       get (sos_Cursor);        // redefined (-> Collection)
  223.  
  224.    void         remove_at (sos_Cursor);        // redefined (-> sos_Aggregate)
  225.    sos_Int      card ();            // redefined (-> sos_Aggregate)
  226.    sos_Cursor   open_cursor (sos_Container = TEMP_CONTAINER);
  227.                         // redefined (-> sos_Aggregate)
  228.    void         close_cursor (sos_Cursor);    // redefined (-> sos_Aggregate)
  229.    sos_Cursor   duplicate (sos_Cursor);        // redefined (-> sos_Aggregate)
  230.    sos_Bool     is_valid(sos_Cursor);        // redefined (-> sos_Aggregate)
  231.    sos_Bool     to_first(sos_Cursor);        // redefined (-> sos_Aggregate)
  232.    sos_Bool     to_last(sos_Cursor);        // redefined (-> sos_Aggregate)
  233.    sos_Bool     to_succ (sos_Cursor, sos_Int=1);// redefined (-> sos_Aggregate)
  234.    sos_Bool     to_pred (sos_Cursor, sos_Int=1);// redefined (-> sos_Aggregate)
  235.  
  236. protected:
  237.    static void     local_initialize (Array<Entity>);
  238.    static void     local_finalize (Array<Entity>);
  239.  
  240.    static void     local_assign (Array<Entity>, sos_Object);
  241.    static sos_Bool local_equal (Array<Entity>, sos_Object, sos_Eq_kind);
  242.    static sos_Int  local_hash_value (Array<Entity>);
  243.  
  244. private:
  245.    Index          bottom_index = bottom;
  246.    Index          top_index = top;
  247.    sos_Offset     address;
  248.    sos_Int        element_size();
  249.  
  250. }; // ** Array<Entity> **
  251.  
  252. // *******************************  Mapping  *******************************
  253.  
  254. class Mapping<Key, Info> (sos_Bool list_cursor = FALSE,
  255.               sos_Bool key_based_on_equal = FALSE,
  256.               sos_Bool info_based_on_equal = FALSE)
  257.    : Association<Key, Info> (key_based_on_equal, info_based_on_equal)
  258. // list_cursor allowes that the mapping could be dynamically modified
  259. // while a cursor iterates over the structur.
  260. {
  261. public:
  262.  
  263.    sos_Bool     is_key (Key);                   // checks if there's an entry for
  264.                         // the given key
  265.    sos_Bool     is_info (Info);                 // checks if there's an entry for
  266.                         // the given info
  267.  
  268.    void         insert (Key, Info);             // if there already exists such an
  269.                         // entry, the Info will be
  270.                         // replaced
  271.    void        remove (Key);                   // deletes an entry
  272.  
  273.    Info         operator[] (Key);               // associative access
  274.  
  275.    // ** sos_Cursor operations **
  276.  
  277.    Key          get_key (sos_Cursor);              // get the current Key value
  278.    Info         get_info (sos_Cursor);               // set the current Info value
  279.    void         set_info (sos_Cursor, Info);           // set the current Info value
  280.    void         move_cursor (sos_Cursor, Key);         // move cursor to Key
  281.  
  282.    void         insert_before (sos_Cursor, Key, Info); // insert (Key, Info)
  283.                                // before cursor position
  284.    void         insert_after (sos_Cursor, Key, Info);  // insert (Key,Info)
  285.                                // after cursor position
  286.  
  287.    // ** Redefinitions **
  288.  
  289.    sos_Int      size ();            // redefined (-> sos_Object)
  290.  
  291.    sos_Bool     is_role1 (Key);            // redefined (-> Association)
  292.    sos_Bool     is_role2 (Info);        // redefined (-> Association)
  293.    Key          get_role1 (sos_Cursor);         // redefined (-> Association)
  294.    Info         get_role2 (sos_Cursor);        // redefined (-> Association)
  295.    void         clear();            // redefined (-> Association)
  296.  
  297.    void         remove_at (sos_Cursor);        // redefined (-> sos_Aggregate)
  298.    sos_Int      card ();            // redefined (-> sos_Aggregate)
  299.    sos_Cursor   open_cursor (sos_Container = TEMP_CONTAINER);
  300.                         // redefined (-> sos_Aggregate)
  301.    void         close_cursor(sos_Cursor);    // redefined (-> sos_Aggregate)
  302.    sos_Cursor   duplicate(sos_Cursor);        // redefined (-> sos_Aggregate)
  303.    sos_Bool     is_valid(sos_Cursor);        // redefined (-> sos_Aggregate)
  304.    sos_Bool     to_first(sos_Cursor);        // redefined (-> sos_Aggregate)
  305.    sos_Bool     to_last(sos_Cursor);        // redefined (-> sos_Aggregate)
  306.    sos_Bool     to_succ (sos_Cursor, sos_Int=1);    // redefined (-> sos_Aggregate)
  307.    sos_Bool     to_pred (sos_Cursor, sos_Int=1);    // redefined (-> sos_Aggregate)
  308.  
  309. protected:
  310.    static void     local_initialize (Mapping<Key,Info>);
  311.    static void     local_finalize (Mapping<Key,Info>);
  312.  
  313.    static void     local_assign (Mapping<Key,Info>, sos_Object);
  314.    static sos_Bool local_equal (Mapping<Key,Info>, sos_Object, sos_Eq_kind);
  315.    static sos_Int  local_hash_value (Mapping<Key,Info>);
  316.  
  317. private:
  318.    sos_Int      cardinality;
  319.    sos_Object   first_object;
  320.    sos_Object   last_object;
  321.    sos_Bool     list_cursor = list_cursor;
  322.    sos_Offset   no_of_pages_offset;
  323.    sos_Int      no_of_pages;
  324.    sos_Int      no_of_page_lists;
  325.    sos_Int      global_depth;
  326.    sos_Int      ht_entries;
  327.    sos_Int      ht_offset;
  328.  
  329.    void         init_table ();
  330.    void         increase_hash_table ();
  331.    void         decrease_hash_table ();
  332.    void         insert_in_list (sos_Object, sos_Object, sos_Object, sos_Object);
  333.    void         insert_in_page_list (sos_Container, sos_Bool, sos_Bool,
  334.                      sos_Offset, sos_Int, sos_Object,
  335.                      sos_Object, sos_Object, sos_Object);
  336.    sos_Object   remove_from_page_list (sos_Container, sos_Bool, sos_Bool,
  337.                        sos_Offset, sos_Int, sos_Object);
  338.    sos_Bool     assemble_page (sos_Offset, sos_Char, sos_Int);
  339.    void         split_page (sos_Container,sos_Bool, sos_Offset, sos_Char,
  340.                 sos_Int, sos_Int);
  341.    sos_Object   search_succ_pred (sos_Object, sos_Int);
  342.    void         write_succ_pred (sos_Container,sos_Bool,sos_Bool,sos_Object,
  343.                  sos_Bool, sos_Object);
  344.  
  345. }; // ** Mapping<Key, Info> **
  346.  
  347. // ******************************    Bag     *******************************
  348.  
  349. class Bag<Entity> (sos_Bool list_cursor = TRUE,
  350.            sos_Bool based_on_equal = FALSE)
  351.    : Collection<Entity> (based_on_equal)
  352.    // list_cursor allowes that the bag could be dynamically modified
  353.    // while a cursor iterates over the structur.
  354. {
  355. public:
  356.    sos_Int      insert     (Entity);      // insert (perhaps again)
  357.    sos_Int      remove     (Entity);      // remove (only one occurrence)
  358.    void        eliminate  (Entity);      // removes all entries of Entity
  359.    sos_Int      occurrences (Entity);     // number of occ. of Entity in Bag
  360.    void         operator+= (Bag<Entity>); // addition
  361.    void         operator-= (Bag<Entity>); // difference
  362.    void         operator*= (Bag<Entity>); // intersection
  363.    sos_Bool     operator<  (Bag<Entity>); // part of
  364.    sos_Bool     operator<= (Bag<Entity>); // part of
  365.    sos_Bool     operator>  (Bag<Entity>); // contains
  366.    sos_Bool     operator>= (Bag<Entity>); // contains
  367.    void         max_union  (Bag<Entity>); // union
  368.  
  369.    // ** sos_Cursor operations **
  370.  
  371.    sos_Int      entity_occurs (sos_Cursor); // number of occ. of current Entity
  372.    sos_Bool     to_diff_succ (sos_Cursor, sos_Int = 1);
  373.    sos_Bool     to_diff_pred (sos_Cursor, sos_Int = 1);
  374.  
  375.    // ** Redefinitions **
  376.  
  377.    sos_Bool     is_element (Entity);        // redefined (-> Collection)
  378.    Entity       get (sos_Cursor);        // redefined (-> Collection)
  379.    void         clear();            // redefined (-> Collection)
  380.  
  381.    void         remove_at (sos_Cursor);        // redefined (-> sos_Aggregate)
  382.    sos_Int      card ();            // redefined (-> sos_Aggregate)
  383.    sos_Cursor   open_cursor (sos_Container = TEMP_CONTAINER);
  384.                         // redefined (-> sos_Aggregate)
  385.    void         close_cursor (sos_Cursor);    // redefined (-> sos_Aggregate)
  386.    sos_Cursor   duplicate (sos_Cursor);        // redefined (-> sos_Aggregate)
  387.    sos_Bool     is_valid(sos_Cursor);        // redefined (-> sos_Aggregate)
  388.    sos_Bool     to_first(sos_Cursor);        // redefined (-> sos_Aggregate)
  389.    sos_Bool     to_last(sos_Cursor);        // redefined (-> sos_Aggregate)
  390.    sos_Bool     to_succ (sos_Cursor, sos_Int=1);// redefined (-> sos_Aggregate)
  391.    sos_Bool     to_pred (sos_Cursor, sos_Int=1);// redefined (-> sos_Aggregate)
  392.  
  393. protected:
  394.    static void     local_initialize (Bag<Entity>);
  395.    static void     local_finalize (Bag<Entity>);
  396.  
  397.    static void     local_assign (Bag<Entity>, sos_Object);
  398.    static sos_Bool local_equal (Bag<Entity>, sos_Object, sos_Eq_kind);
  399.    static sos_Int  local_hash_value (Bag<Entity>);
  400.  
  401. private:
  402.    sos_Int                  cardinality;
  403.    Mapping<Entity,sos_Int>    m;
  404.  
  405.    void          search_succ_pred (sos_Bag_node, Index, sos_Object&, sos_Int&,
  406.                    sos_Int&);
  407.    void          write_current (sos_Cursor, sos_Object, sos_Int, sos_Int);
  408.    sos_Int       get_no_of_elements (Mapping<Entity,sos_Int>, sos_Object);
  409.    sos_Int       set_no_of_elements (Mapping<Entity,sos_Int>, sos_Object,
  410.                      sos_Int, sos_Int);
  411.    sos_Bool      list_cursor = list_cursor;
  412.  
  413. }; // ** Bag<Entity> **
  414.  
  415. // ******************************    Set     *******************************
  416.  
  417. class Set<Entity> (sos_Bool list_cursor = TRUE,
  418.            sos_Bool based_on_equal = FALSE)
  419.    : Collection<Entity> (based_on_equal)
  420.    // list_cursor allowes that the set could be dynamically modified
  421.    // while a cursor iterates over the structur.
  422. {
  423. public:
  424.    // ** Set operators **
  425.    void         insert     (Entity);      // insertion - union (perhaps again)
  426.    void         remove     (Entity);      // removal / difference
  427.    void         operator+= (Set<Entity>); // addition
  428.    void         operator-= (Set<Entity>); // difference
  429.    void         operator*= (Set<Entity>); // intersection
  430.    sos_Bool     operator<  (Set<Entity>); // part of
  431.    sos_Bool     operator<= (Set<Entity>); // part of
  432.    sos_Bool     operator>  (Set<Entity>); // contains
  433.    sos_Bool     operator>= (Set<Entity>); // contains
  434.  
  435.    // ** Redefinitions **
  436.  
  437.    sos_Bool     is_element (Entity);        // redefined (-> Collection)
  438.    Entity       get (sos_Cursor);        // redefined (-> Collection)
  439.    void         clear();            // redefined (-> Collection)
  440.  
  441.    void         remove_at (sos_Cursor);        // redefined (-> sos_Aggregate)
  442.    sos_Int      card ();            // redefined (-> sos_Aggregate)
  443.    sos_Cursor   open_cursor (sos_Container = TEMP_CONTAINER);
  444.                         // redefined (-> sos_Aggregate)
  445.    void         close_cursor (sos_Cursor);    // redefined (-> sos_Aggregate)
  446.    sos_Cursor   duplicate (sos_Cursor);        // redefined (-> sos_Aggregate)
  447.    sos_Bool     is_valid(sos_Cursor);        // redefined (-> sos_Aggregate)
  448.    sos_Bool     to_first(sos_Cursor);        // redefined (-> sos_Aggregate)
  449.    sos_Bool     to_last(sos_Cursor);        // redefined (-> sos_Aggregate)
  450.    sos_Bool     to_succ (sos_Cursor, sos_Int=1);// redefined (-> sos_Aggregate)
  451.    sos_Bool     to_pred (sos_Cursor, sos_Int=1);// redefined (-> sos_Aggregate)
  452.  
  453. protected:
  454.    static void     local_initialize (Set<Entity>);
  455.    static void     local_finalize (Set<Entity>);
  456.  
  457.    static void     local_assign (Set<Entity>, sos_Object);
  458.    static sos_Bool local_equal (Set<Entity>, sos_Object, sos_Eq_kind);
  459.    static sos_Int  local_hash_value (Set<Entity>);
  460.  
  461. private:
  462.    sos_Bool             list_cursor = list_cursor;
  463.    Mapping<Entity,sos_Bool>  m;
  464.  
  465. }; // ** Set<Entity> **
  466.  
  467. // *****************************    sos_Node    *****************************
  468. // only for sos_Internal use!
  469.  
  470. class sos_Node {};
  471.  
  472. // **************************    sos_Array_node    **************************
  473.  
  474. class sos_Array_node : sos_Node
  475. {
  476.    friend class Array;
  477. private:
  478.    Index index;
  479.  
  480. }; // ** sos_Array_node **
  481.  
  482.  
  483. // ***************************    sos_List_node    **************************
  484.  
  485. class sos_List_node : sos_Node
  486. {
  487.    friend class List;
  488. private:
  489.    local sos_List_node succ, pred;
  490.  
  491.    sos_Object    val;            // contents of the node
  492.  
  493.    void          insert_before (sos_List_node);
  494.    void          insert_after  (sos_List_node);
  495.    void          remove ();
  496.    sos_List_node succ (sos_Int steps = 1);
  497.    sos_List_node pred (sos_Int steps = 1);
  498.  
  499. }; // ** sos_List_node **
  500.  
  501. // *****************************  sos_Map_node  *****************************
  502.  
  503. class sos_Map_node : sos_Node
  504. {
  505.    friend class Mapping;
  506. protected:
  507.    sos_Object    key_val;
  508.  
  509. }; // ** sos_Map_node **
  510.  
  511. // ***************************** sos_Bag_node  *****************************
  512.  
  513. class sos_Bag_node : sos_Map_node
  514. {
  515.    friend class Bag;
  516. private:
  517.    sos_Int       tag_no;
  518.    sos_Int       tag_max;
  519.  
  520. }; // ** sos_Bag_node **
  521.  
  522. } // ** schema agg **
  523.